Find all good strings [KMP Algorithm]¶
Time: O(MxN); Space: O(M); hard
Given the strings s1 and s2 of size n, and the string evil. Return the number of good strings.
A good string has size n, it is alphabetically greater than or equal to s1, it is alphabetically smaller than or equal to s2, and it does not contain the string evil as a substring. Since the answer can be a huge number, return this modulo 10^9 + 7.
Example 1:
Input: n = 2, s1 = “aa”, s2 = “da”, evil = “b”
Output: 51
Explanation:
There are 25 good strings starting with ‘a’: “aa”,“ac”,“ad”,…,“az”. Then there are 25 good strings starting with ‘c’: “ca”,“cc”,“cd”,…,“cz” and finally there is one good string starting with ‘d’: “da”.
Example 2:
Input: n = 8, s1 = “leetcode”, s2 = “leetgoes”, evil = “leet”
Output: 0
Explanation:
All strings greater than or equal to s1 and smaller than or equal to s2 start with the prefix “leet”, therefore, there is not any good string.
Example 3:
Input: n = 2, s1 = “gx”, s2 = “gz”, evil = “x”
Output: 2
Constraints:
s1.length == n
s2.length == n
s1 <= s2
1 <= n <= 500
1 <= evil.length <= 50
All strings consist of lowercase English letters.
Hints:
Use DP with 4 states (pos: Int, posEvil: Int, equalToS1: Bool, equalToS2: Bool) which compute the number of valid strings of size “pos” where the maximum common suffix with string “evil” has size “posEvil”. When “equalToS1” is “true”, the current valid string is equal to “S1” otherwise it is greater. In a similar way when equalToS2 is “true” the current valid string is equal to “S2” otherwise it is smaller.
To update the maximum common suffix with string “evil” use KMP preprocessing.
1. Dynamic programming (KMP algorithm) [O(N^2), O(N)]¶
[3]:
class Solution1(object):
"""
Time: O(M*N)
Space: O(M)
"""
def findGoodStrings(self, n, s1, s2, evil):
"""
:type n: int
:type s1: str
:type s2: str
:type evil: str
:rtype: int
"""
MOD = 10**9+7
def getPrefix(pattern):
prefix = [-1]*len(pattern)
j = -1
for i in range(1, len(pattern)):
while j != -1 and pattern[j+1] != pattern[i]:
j = prefix[j]
if pattern[j+1] == pattern[i]:
j += 1
prefix[i] = j
return prefix
prefix = getPrefix(evil)
dp = [[[[0]*len(evil) for _ in range(2)] for _ in range(2)] for _ in range(2)]
dp[0][0][0][0] = 1
for i in range(n):
dp[(i+1)%2] = [[[0]*len(evil) for _ in range(2)] for _ in range(2)]
for j in range(2):
for k in range(2):
min_c = 'a' if j else s1[i]
max_c = 'z' if k else s2[i]
for l in range(len(evil)):
if not dp[i%2][j][k][l]:
continue
for c in range(ord(min_c)-ord('a'), ord(max_c)-ord('a')+1):
c = chr(c+ord('a'))
m = l-1
while m != -1 and evil[m+1] != c:
m = prefix[m]
if evil[m+1] == c:
m += 1
if m+1 == len(evil):
continue
dp[(i+1)%2][j or (s1[i] != c)][k or (s2[i] != c)][m+1] = \
(dp[(i+1)%2][j or (s1[i] != c)][k or (s2[i] != c)][m+1] + dp[i%2][j][k][l]) % MOD
result = 0
for j in range(2):
for k in range(2):
for l in range(len(evil)):
result = (result + dp[n%2][j][k][l]) % MOD
return result
[4]:
s = Solution1()
n = 2
s1 = "aa"
s2 = "da"
evil = "b"
assert s.findGoodStrings(n, s1, s2, evil) == 51
n = 8
s1 = "leetcode"
s2 = "leetgoes"
evil = "leet"
assert s.findGoodStrings(n, s1, s2, evil) == 0
n = 2
s1 = "gx"
s2 = "gz"
evil = "x"
assert s.findGoodStrings(n, s1, s2, evil) == 2